/**
 * 【贪心算法】背包问题
 * @param {Array<number>} weights 
 * @param {Array<number>} values 
 * @param {number} capacity
 * @returns {number}
 */
export const knapSack = (weights, values, capacity) => {
    const objectList = []
    // 遍历物品，构建物品的详细信息（算出性价比）
    for (let i = 0; i < weights.length; i++) {
        objectList.push({
            index: i,
            weight: weights[i],
            value: values[i],
            costEffient: values[i] / weights[i]
        })
    }
    // 按照性价比给物品排序
    objectList.sort((a, b) => b.costEffient - a.costEffient)

    const knapSack = {
        productInKnapSack: [],
        value: 0,
        weight: 0,
        capacity: capacity
    }

    // 将物品按照性价比由高到低放入背包，放不下的切开来放进去能放进去的部分
    for (let i = 0; i < objectList.length; i++) {
        if (knapSack.capacity >= objectList[i].weight) {
            knapSack.productInKnapSack.push({ ...objectList[i], ratio: 1 })
            knapSack.value += objectList[i].value
            knapSack.weight += objectList[i].weight
            knapSack.capacity -= objectList[i].weight
        } else if (knapSack.capacity > 0) {
            const ratio = knapSack.capacity / objectList[i].weight
            knapSack.productInKnapSack.push({ ...objectList[i], ratio })
            knapSack.value += (objectList[i].value * ratio)
            knapSack.weight += objectList[i].weight * ratio
            knapSack.capacity -= objectList[i].weight * ratio
            break
        } else {
            break
        }
    }

    console.log('knapSack:', knapSack)
    return knapSack.value
}